package leetcode.btodo;

/**
 * 实现正则表达式
 *
 * @date 2020/3/23 17:52
 */
public class Code10_Regular {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        return s.matches("^" + p + "$");
        // return matchStr(s.toCharArray(),0,pattern,0);
    }

    private boolean matchStr(char[] str, int i, char[] pattern, int j) {
        //都匹配完了，或者二者都是空串
        if (i == str.length && j == pattern.length) {
            return true;
            // i < str.length ,pattern已经匹配完了但是字符串没有匹配完
        } else if (j == pattern.length) {
            return false;
        }
        // 有可能 i = str.length 但是 j < pattern.length

        //如果匹配串的 下一个位置是 * ，要做两种处理
        if ((j + 1 < pattern.length) && pattern[j + 1] == '*') {

            //当 str[i] == pattern[j] || pattern[j] == '.' ,可以匹配0个或1个或多个
            if (i < str.length && (str[i] == pattern[j] || pattern[j] == '.')) {
                return
                        //匹配多个
                        matchStr(str, i + 1, pattern, j) ||
                                //匹配1个
                                matchStr(str, i + 1, pattern, j + 2);
                //匹配0个，如b   b*b，虽然b = b,但是也可以忽略,如果不加第三个分支 ，那么这个会返回false
                //  ||  matchStr(str,i,pattern,j+2);
            } else {
                //否则肯定是匹配0个,如ab   c*ab*, a！=c  或者 i已经到头，如ab  abc*d*e*
                return matchStr(str, i, pattern, j + 2);
            }

            //pattern下一个位置不是 * 或者j == pattern.length -1
        } else {
            //如果二者一样或者是 匹配任意字符
            if (i < str.length && (str[i] == pattern[j] || pattern[j] == '.')) {
                return matchStr(str, i + 1, pattern, j + 1);
            } else {
                //否则匹配不上
                return false;
            }
        }
    }


    public static void main(String[] args) {

    }
}
